class ListNode(object):
    def __init__(self, data, next=None):
        self.val = data
        self.next = next


class LindedLsit(object):
    def __init__(self):
        self.head = None

    def initList(self, data):
        self.head = ListNode(data[0])

        p = self.head
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return self.head


def traveList(head):
    # if self.isEmpty():
    #     exit(0)
    p = head
    while p:
        print(p.val)
        p = p.next


def merge_two_lists(l1, l2):
    dummy = ListNode(-1)
    p = dummy
    p1 = l1
    p2 = l2

    while p1 != None and p2 != None:
        if p1.val > p2.val:
            p.next = p2
            p2 = p2.next
        else:
            p.next = p1
            p1 = p1.next
        p = p.next

    if p1 != None:
        p.next = p1
    if p2 != None:
        p.next = p2
    return dummy.next


from typing import *


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param lists ListNode类一维数组
# @return ListNode类
#
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # write code here
        if not lists:
            return None
        return self.mergeAll(lists, 0, len(lists) - 1)

    def mergeAll(self, lists, low, high):
        if low >= high:
            return lists[low]
        mid = int((high + low) / 2)
        l1 = self.mergeAll(lists, low, mid)
        l2 = self.mergeAll(lists, mid + 1, high)
        return self.merge(l1, l2)

    # def merge(self, l1, l2):
    #     dummy = ListNode(-1)
    #     if l1 == None:
    #         return l2
    #     if l2 == None:
    #         return l1
    #
    #     if l1.val < l2.val:
    #         l1.next = self.merge(l1.next, l2)
    #         return l1
    #     else:
    #         l2.next = self.merge(l1, l2.next)
    #         return l2

    def merge(self,l1,l2):
        dummy = ListNode(-1)
        p = dummy
        while l1 != None and l2 !=None:
            if l1.val > l2.val:
                p.next = l2
                l2 = l2.next
            else:
                p.next = l1
                l1 = l1.next
            p = p.next

        if l1 != None:
            p.next =l1
        if l2 != None:
            p.next = l2
        return p.next


if __name__ == "__main__":
    data1 = [1, 3, 5, 7, 9]
    data2 = [2, 4, 6, 8, 10]
    linked_list = LindedLsit()
    head1 = linked_list.initList(data1)
    head2 = linked_list.initList(data2)
    head = merge_two_lists(head2, head1)
    traveList(head)
